1. Field of the Invention
The present invention relates to an apparatus, method, and computer program for verifying a logic circuit, and more particularly to an apparatus, method, and computer program for verifying a circuit that operates with two or more clock signals.
2. Description of the Related Art
The design of semiconductor integrated circuits becomes more and more complex to implement many functions densely into a single chip. This leads to an increased need for more accurate and less time-consuming simulation and verification techniques. Particularly in communications applications, the circuit may use different clocks for sending and receiving signals. An interface between two circuits operating with different clocks is referred to as a clock domain crossing (CDC) path. CDC paths are susceptible to metastability problems, which cannot be tested by an ordinary logical verification process. It is therefore important, when testing such a logic circuit, to verify the effects of metastability on its internal CDC paths.
As an example of metastability, FIGS. 12A and 12B show how a flip-flop circuit 500 behaves when it encounters metastability. Specifically, FIG. 12B is a timing diagram showing relationships between a clock input signal CK, a data input signal D, and an output signal Q, where the symbols C1, C2, C3, and C4 represent four consecutive clock cycle periods. In the case where the data input signal D is high at a rising edge of clock signal CK in cycle C2, the output signal Q is supposed to go up at the beginning of cycle C2. If the change of the data input signal D occurs immediately before that clock edge, the output signal Q may rise, not in cycle C2, but in cycle C3, thus causing a delay of data propagation. As this example shows, the output Q of a flip-flop 500 can become unstable in the case where its data input signal D changes immediately before or after the rising edge of clock signal CK. This condition is known as metastability.
CDC paths may encounter metastability particularly when the input signal changes during a short period in which two different clock signals rise nearly at the same time. FIGS. 13 and 14 show an example of failure caused by metastability at a CDC path. Specifically, FIG. 13 shows a logic circuit operating with two clock signals clk1 and clk2. An input signal D1 is supplied to one input of an AND gate 501 and to a flip-flop 502, whose output is fed to another flip-flop 503. The output signal (D1t) of this flip-flop 503 is then supplied to a subsequent flip-flop 504. In other words, the flip-flops 502, 503, and 504 are connected in series.
Another input signal D2 is entered to the other input terminal of the AND gate 501. The output of this AND gate 501 is fed to a flip-flop 505, and the output of that flip-flop 505 is directed to another flip-flop 506. The output signal (D2t) of the flip-flop 506 is supplied to a subsequent flip-flop 507. In other words, the flip-flops 505, 506, and 507 are connected in series. An AND gate 508 receives the output signals of flip-flops 504 and 507 and sends its own output to yet another flip-flop 509. This flip-flop 509 produces an output signal OUT, the final result of logic operations performed by the circuit of FIG. 13.
In the logic circuit of FIG. 13, one group of flip-flops 502 and 505 operates with a first clock signal clk1, while the other group of flip-flops 503, 504, 506, 507, and 509 operates with a second clock signal clk2. The flip-flops 502 and 503 are connected in series while they belong to different clock domains. The connection between these two flip-flops 502 and 503 constitutes a CDC path 510, which is subject to the effects of metastability. Likewise, the connection between two flip-flops 505 and 506 constitutes another CDC path 511, which is also subject to the effects of metastability.
As FIG. 14 shows, the input signal D1 changes at a rising edge of the first clock signal clk1 during cycle C11, the new state of which is taken into flip-flops 502 and 505 at the next rising edge of clk1. Flip-flops 503 and 506 capture the outputs of the flip-flops 502 and 505 at a rising edge of the second clock signal clk2 during cycle C21. From the viewpoint of clk2 domain, however, the change in those outputs may be too close to that rising edge of clk2 for the flip-flops 503 and 506 to take in the new signal state correctly, which could thus cause a metastability. FIG. 14 shows an example of such results. Specifically, the flip-flop 503 outputs a signal D1t that changes in synchronization with a rising edge of clk2, which, in the present case, goes high in cycle C22 with a one-clock delay. The flip-flop 506 in the other CDC path 511, on the other hand, may operate in an expected way, changing its output D2t at a rising edge of clk2 during cycle C21. If this is the case, the output signal OUT will stay low in cycle C23 although that cycle is where the signal OUT is supposed to be asserted.
Researchers in this field have proposed several techniques to test such effects of metastability in a logic circuit design. See, for example, Japanese Unexamined Patent Application Publication Nos. 2005-284426 and 2001-229211. One proposed technique forces CDC paths to produce signal delays so as to determine whether the circuit under test is immune to metastability.
FIG. 15 gives an overview of a conventional verification apparatus. This verification apparatus 600 is formed from the following elements: a circuit database 601, a CDC detector 602, a CDC path database 603, a delay generator inserter 604, a delay-insertable circuit database 605, a verifier 606, and a scenario database 607. The circuit database 601 stores data of a circuit under test. The CDC detector 602 searches the circuit under test to find CDC paths in the circuit under test, and the CDC path database 603 records each found CDC path. The delay generator inserter 604 inserts a delay generator to each CDC path so as to emulate a signal delay that could be induced by metastability. The delay-insertable circuit database 605 stores data of circuit which includes such delay generators. The verifier 606 verifies the circuit under test by giving a specific simulation pattern to the delay-insertable circuit. Such simulation patterns are referred to herein as “scenarios,” and the scenario database 607 stores a plurality of scenarios for simulation.
FIG. 16 is a flowchart showing a conventional verification method. First, the CDC detector 602 searches the circuit database 601 to find CDC paths in the circuit under test (step S90). When a CDC path is found, the delay generator inserter 604 inserts a delay generator to that path (step S91). The verifier 606 determines whether all scenarios stored in the scenario database 607 have been tested (step S92), and if so, the verifier 606 terminates the test. If there are untested scenarios, the verifier 606 selects a new specific scenario from those stored in the scenario database 607 (step S93).
Now that a scenario is selected, the verifier 606 chooses randomly a CDC path in the circuit under test and simulates the behavior of the circuit. During this simulation, the verifier 606 activates an embedded delay generator to forcibly produce a delay in the CDC path, assuming the occurrence of metastability (step S94). The verifier 606 determines whether any failure is found in the simulation (step S95). If there is a failure, the verification apparatus 600 permits the user to modify the circuit (step S96) and then returns to step S90 to repeat the above process. If there are no failures found, then the verification apparatus 600 determines whether the simulation has been done as many times as specified (step S97). If so, the verification apparatus 600 goes back to step S92 to attempt another scenario. If not, the verification apparatus 600 returns to step S94 to choose another CDC path to continue the simulation. The conventional verification apparatus 600 operates in this way to test a logic circuit, considering the effects of metastability.
Japanese Unexamined Patent Application Publication No. 2005-31890 discloses a technique to analyze a sequential circuit susceptible to metastability. This technique assigns an abnormal delay time to a specified sequential circuit to simulate the effect of metastability, while assigning normal delay times to other circuits.
The effects of metastability may not always manifest themselves at outputs of the circuit. Rather, there are many such cases where a metastable state is confined within a limited portion of the circuit and never appears at its output pins. FIG. 17 is a timing diagram showing an example case where the circuit's output is not affected by delays in a CDC path. This example is a result of a simulation using a specific scenario for the circuit discussed in FIG. 13.
In the case, for example, where the input signal D1 is fixed at a low level, one input of the AND gate 508 (FIG. 13) is always driven to low, meaning that the output of the AND gate 508 will never become high. While the second CDC path 511 may encounter metastability, the resulting one-clock delay in signal D2t (see FIG. 17) would not affect the output signal OUT. This means that the behavior of the circuit of FIG. 13 does not change in this particular scenario, no matter whether metastability occurs or not. In other words, it is a waste of time to test the effects of metastability when such a scenario is selected. The foregoing conventional verification methods apply all scenarios exhaustively, despite the fact that some of those scenarios do not affect outputs of the circuit under test. Trying every scenario in this case means consuming a long time to verify the circuit.